#include <bits/stdc++.h>
using namespace std;

/*
2563. 统计公平数对的数目
已解答
中等
相关标签
相关企业
提示
给你一个下标从 0 开始、长度为 n 的整数数组 nums ，和两个整数 lower 和 upper ，返回 公平数对的数目 。

如果 (i, j) 数对满足以下情况，则认为它是一个 公平数对 ：

0 <= i < j < n，且
lower <= nums[i] + nums[j] <= upper
 

示例 1：

输入：nums = [0,1,7,4,4,5], lower = 3, upper = 6
输出：6
解释：共计 6 个公平数对：(0,3)、(0,4)、(0,5)、(1,3)、(1,4) 和 (1,5) 。
示例 2：

输入：nums = [1,7,9,2,5], lower = 11, upper = 11
输出：1
解释：只有单个公平数对：(2,3) 。
 

提示：

1 <= nums.length <= 105
nums.length == n
-109 <= nums[i] <= 109
-109 <= lower <= upper <= 109
*/

// 法一
using ll = long long;
class Solution {
private:
    long long countLessEqual(vector<int>& nums, int tar) {
        ll ans = 0;
        int left = 0;
        int right = nums.size() - 1;
        while (left < right) {
            int sum = nums[left] + nums[right];
            if (sum <= tar) {
                ans += right - left;    // 统计所有以left为左端的合法数对
                left++;         // 指针右移
            } else {
                right--;        // 指针左移
            }
        }
        return ans;
    }
public:
    long long countFairPairs(vector<int>& nums, int lower, int upper) {
        // 先排序数组 双指针
        sort(nums.begin(), nums.end());
        ll count_upper = countLessEqual(nums, upper);
        ll count_lower = countLessEqual(nums, lower - 1);
        return count_upper - count_lower;
    }
};

// 法二
class Solution {
public:
	long long countFairPairs(vector<int>& nums, int lower, int upper) {
		// 首先对数组排序，使得可以使用双指针高效计算区间
		sort(nums.begin(), nums.end());
		long long ans = 0;
		int first = nums.size(); // 初始化指针，用于找满足 nums[i] >= (lower - nums[j]) 的最小索引
		int last = nums.size();  // 初始化指针，用于找满足 nums[i] <= (upper - nums[j]) 的最大索引
		
		for(int j = 0; j < nums.size(); j++) {
			// 计算当前元素 nums[j] 对应的上下界
			int cur_upper = upper - nums[j];
			int cur_lower = lower - nums[j];
			
			// 调整 first 指针：从右向左找到第一个 nums[first-1] < cur_lower 的位置
			// 最终 first 是满足 nums[i] >= cur_lower 的最小索引
			while (first > 0 && nums[first - 1] >= cur_lower) {
				first--;
			}
			
			// 调整 last 指针：从右向左找到第一个 nums[last-1] <= cur_upper 的位置
			// 最终 last 是满足 nums[i] <= cur_upper 的最大索引 +1
			while (last > 0 && nums[last - 1] > cur_upper) {
				last--;
			}
			
			// 有效区间为 [first, last)，且要保证 i < j
			// min(last, j) 确保上界不超过 j-1，min(first, j) 确保下界不超过 j-1
			ans += min(last, j) - min(first, j);
		}
		return ans;
	}
};